import java.util.Arrays;
import java.util.HashMap;

public class ThreeSumClosest {
    /**
     *给你一个长度为 n 的整数数组nums和 一个目标值target。
     * 请你从 nums 中选出三个整数，使它们的和与target最接近。
     * 返回这三个数的和。
     * 假定每组输入只存在恰好一个解。
     * 链接：https://leetcode-cn.com/problems/3sum-closest
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        for (int i=0;i<nums.length-1;i++){
            int temp = Math.abs(target -nums[i]);
            int p =i+1;
            int q =nums.length-1;
            while (p!=q){
                if (nums[p]+nums[q]==temp)
                    return target;
                else if (Math.abs(nums[p]+nums[q])<temp){
                    p++;
                    min = Math.min(min,nums[i]+nums[p]+nums[q]);
                }else {
                    q--;
                    min = Math.min(min,nums[i]+nums[p]+nums[q]);
                }
            }

        }

        return min;

    }
}
